package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QuickSort {

    /**
     * 对数组src进行分区,以k为值分区(k左边都比k小,右边都比k大)
     *
     * @param src 待分区数组
     * @param k   分区数
     * @return int k在array中的为值
     */
    private int partion(int[] src, int k) {

        int j = 1;
        int m = src.length - 1;

        while (j <= m) {
            while (j <= m && src[j] <= k) {
                j++;
            }
            while (j <= m && src[m] > k) {
                m++;
            }
            if (m >= j) {
                int o = src[j];
                src[j] = src[m];
                src[m] = o;
            }

        }
        src[0] = src[j];
        src[j] = k;
        return j;
    }

    public List<Integer> quickSort(List<Integer> ints) {

        if (ints == null) {
            throw new IllegalArgumentException("传入数组为null");
        }

        if (ints.size() < 2) {
            return ints;
        }

        var privot = ints.get(0);


        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
//        ArrayList<Integer> midde = new ArrayList<>();

        for (int i = 0; i < ints.size(); i++) {
            Integer integer = ints.get(i);
//            System.out.println(integer);
            if (integer <privot){
                left.add(integer);
            }
            if (integer >privot){
                right.add(integer);
            }
//            if (integer.equals(privot)){
//                midde.add(integer);
//            }
        }


        result.addAll(quickSort(left));
//        result.addAll(midde);
        result.add(privot);
        result.addAll(quickSort(right));
        return result;
    }

    public static void main(String[] args) {
        List<Integer> integers = Arrays.asList(3, 4,4, 2, 3, 45, 6, 7, 3, 1, 3, 9, 22, 33, 11, 23, 77, 111);
        QuickSort quickSort = new QuickSort();
        System.out.println(quickSort.quickSort(integers));

    }
}
